home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1997 October: Mac OS SDK / Dev.CD Oct 97 SDK1.toast / Development Kits (Disc 1) / QuickDraw GX / Programming Stuff / GX Libraries / CubicLibrary.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-04-07  |  8.9 KB  |  324 lines  |  [TEXT/MPS ]
  1.  
  2. /*
  3.     File:        CubicLibrary.c
  4.  
  5.     Contains:    graphics libraries - cubic library
  6.  
  7.     Written by:    Hugo Ayala
  8.  
  9.     Copyright:    © 1995 by Apple Computer, Inc., all rights reserved.
  10.  
  11.     Change History (most recent first):
  12.  
  13.          <2>      4/7/95    jtd        changed 'fract' to 'Fract'
  14.          <1>      1/9/95    JD        First checked in.
  15. */
  16.  
  17. #include "GraphicsLibraries.h"
  18.  
  19. typedef struct  {       /* this structure contains the cached cubic coefficients */
  20.   Fixed   ax, ay;
  21.   Fixed   bx, by;
  22.   Fixed   cx, cy;
  23.   Fixed   dx, dy;
  24. } xCubic;
  25.  
  26. typedef struct  {       /* this structure is just for a gxPath */
  27.   long    contours;
  28.   long    count;
  29.   long    flags;
  30.   gxPoint   data[ 32 ];
  31. } smallPath;
  32.  
  33.  
  34. /* macros to calculate the inner products */
  35.     
  36. #define XCube(xc,u) (FractMultiply(FractMultiply(FractMultiply((xc)->ax,(u))+(xc)->bx,(u))+(xc)->cx,(u))+(xc)->dx)
  37. #define YCube(xc,u) (FractMultiply(FractMultiply(FractMultiply((xc)->ay,(u))+(xc)->by,(u))+(xc)->cy,(u))+(xc)->dy)
  38.  
  39. #define XCubePrime(xc,u) (FractMultiply(FractMultiply((3*(xc)->ax),(u))+(2*(xc)->bx),(u))+(xc)->cx)
  40. #define YCubePrime(xc,u) (FractMultiply(FractMultiply((3*(xc)->ay),(u))+(2*(xc)->by),(u))+(xc)->cy)
  41.  
  42.  
  43. /* This routine calculates the number of cubics that would be needed to draw a with no more than a pixel error. */
  44. static long xCountQuadratics( const cubic *cube )
  45. {
  46.   Fixed ax = -cube->a.x + 3 * cube->b.x - 3 * cube->c.x + cube->d.x; /* first get the a vector components */
  47.   Fixed ay = -cube->a.y + 3 * cube->b.y - 3 * cube->c.y + cube->d.y;
  48.   short temp;
  49.   long count;
  50.   
  51.   if( ax < 0 )  /* make sure that they are positive */
  52.     ax = -ax;
  53.   if( ay < 0 )
  54.     ay = -ay;
  55.   ax = ( ay < ax ) ? ax : ay; /* pick the max one */
  56.   
  57.    temp = ( FixedDivide( ax, ff( 20 ) ) + 0xFFFF ) >> 16; /* we now divide by twenty and take the ceiling */
  58.  
  59.   /*    NOTE: if you want the tolerance to be .5 then   */
  60.   /*    divide ax by 10, .25 -> 5, etc        */
  61.   
  62.   /* this is a crude but fast and effective way of taking the cube root of    */
  63.   /* 'temp' which is between 0 and 27000                                      */
  64.   
  65.   if( temp <= 4096 ) {
  66.     if( temp <= 512 ) {
  67.       if( temp <= 64 ) {
  68.         if( temp <= 8 ) {
  69.           if( temp <= 1 )
  70.             count = 1;
  71.           else
  72.             count = 2;
  73.         } else {
  74.           if( temp <= 27 )
  75.             count = 3;
  76.           else
  77.             count = 4;
  78.         }
  79.       } else {
  80.         if( temp <= 216 ) {
  81.           if( temp <= 125 )
  82.             count = 5;
  83.           else
  84.             count = 6;
  85.         } else {
  86.           if( temp <= 343 )
  87.             count = 7;
  88.           else
  89.             count = 8;
  90.         }
  91.       }
  92.     } else {
  93.       if( temp <= 1728 ) {
  94.         if( temp <= 1000 ) {
  95.           if( temp <= 729 )
  96.             count = 9;
  97.           else
  98.             count = 10;
  99.         } else {
  100.           if( temp <= 1331 )
  101.             count = 11;
  102.           else
  103.             count = 12;
  104.         }
  105.       } else {
  106.         if( temp <= 2744 ) {
  107.           if( temp <= 2197 )
  108.             count = 13;
  109.           else
  110.             count = 14;
  111.         } else {
  112.           if( temp <= 3375 )
  113.             count = 15;
  114.           else
  115.             count = 16;
  116.         }
  117.       }
  118.     }
  119.   } else {
  120.     if( temp <= 13824 ) {
  121.       if( temp <= 8000 ) {
  122.         if( temp <= 5832 ) {
  123.           if( temp <= 4913 )
  124.             count = 17;
  125.           else
  126.             count = 18;
  127.         } else {
  128.           if( temp <= 6859 )
  129.             count = 19;
  130.           else
  131.             count = 20;
  132.         }
  133.       } else {
  134.         if( temp <= 10648 ) {
  135.           if( temp <= 9261 )
  136.             count = 21;
  137.           else
  138.             count = 22;
  139.         } else {
  140.           if( temp <= 12167 )
  141.             count = 23;
  142.           else
  143.             count = 24;
  144.         }
  145.       }
  146.     } else {
  147.       if( temp <= 21952 ) {
  148.         if( temp <= 17576 ) {
  149.           if( temp <= 15625 )
  150.             count = 25;
  151.           else
  152.             count = 26;
  153.         } else {
  154.           if( temp <= 19683 )
  155.             count = 27;
  156.           else
  157.             count = 28;
  158.         }
  159.       } else {
  160.         if( temp <= 27000 ) {
  161.           if( temp <= 24389 )
  162.             count = 29;
  163.           else
  164.             count = 30;
  165.         } else  /* because our gxPath can only contain 32 -2 points we stop here */
  166.           count = 30;
  167.       }
  168.     }
  169.   }
  170.   return  count;
  171. }
  172.  
  173.  
  174. /* This routine is where the cuadratic points get computed.  Note that this
  175.   routine never fills in the last gxPoint in the code. It also assumes that the first gxPoint has been moved in by the caller.
  176.     
  177.   cubic     ->      a pointer to the cubic
  178.   count   ->      the number of points other than the two end ones that we need to generate
  179.   storage   ->      a place to put the points that are generated
  180. */
  181. static gxPoint *ComputePoints( const cubic *cube, long count,  gxPoint *storage )
  182. {
  183.   Fixed  *ptr = &storage->x;
  184.   
  185.   if( 0 < count )
  186.   { xCubic x;
  187.     Fract  n  = FractDivide( 1, count );      /*    LongInt / LongInt -> frac   */
  188.     Fract u = n;
  189.     Fixed tempx1 = cube->a.x >> 1;  
  190.     Fixed tempy1 = cube->a.y >> 1;
  191.     Fixed tempx2, tempy2;
  192.     
  193.     /* we compute the coefficients for this cubic -- for efficient computation later  */
  194.     
  195.     x.ax = -cube->a.x + 3 * cube->b.x - 3 * cube->c.x + cube->d.x;
  196.     x.ay = -cube->a.y + 3 * cube->b.y - 3 * cube->c.y + cube->d.y;
  197.     x.bx = 3 * cube->a.x - 6 * cube->b.x + 3 * cube->c.x;
  198.     x.by = 3 * cube->a.y - 6 * cube->b.y + 3 * cube->c.y;
  199.     x.cx = -3 * cube->a.x + 3 * cube->b.x;
  200.     x.cy = -3 * cube->a.y + 3 * cube->b.y;
  201.     x.dx = cube->a.x;
  202.     x.dy = cube->a.y;
  203.     tempx2 = FractMultiply( x.cx, n ) >> 2;
  204.     tempy2 = FractMultiply( x.cy, n ) >> 2;
  205.     
  206.     for( ; 0 < count; --count )  
  207.     { Fixed ntempx1 = XCube( &x, u ) >> 1;  /* compute the next gxPoint sequence */
  208.       Fixed ntempy1 = YCube( &x, u ) >> 1;
  209.       Fixed  ntempx2 = FractMultiply( XCubePrime( &x, u ), n ) >> 2;
  210.       Fixed ntempy2 = FractMultiply( YCubePrime( &x, u ), n ) >> 2;
  211.         
  212.       *ptr++ = tempx1 + tempx2 + ntempx1 - ntempx2; /* store the gxPoint */
  213.       *ptr++ = tempy1 + tempy2 + ntempy1 - ntempy2;
  214.       tempx1 = ntempx1;
  215.       tempx2 = ntempx2;
  216.       tempy1 = ntempy1;
  217.       tempy2 = ntempy2;
  218.       u += n;
  219.     }
  220.     *ptr++ = cube->d.x;  /* move in the last gxPoint of the cubic */
  221.     *ptr++ = cube->d.y;
  222.   }
  223.   return (gxPoint *) ptr;
  224. }
  225.  
  226.  
  227. /* This routine fills in a data structure for a gxPath with the information of a cubic.
  228.   pathptr   ->    a pointer to the gxPath
  229.   cube      ->    the cubic
  230.   count   ->    how many points to use
  231. */
  232. static void CubicPath( smallPath *pathptr, const cubic *cube, const long count )
  233. {
  234.   gxPoint  *ptr;
  235.  
  236.   pathptr->contours = 1;
  237.   pathptr->count = count + 2;
  238.   pathptr->flags = ~((unsigned long) 0x80000000 >> count + 1) & 0x7FFFFFFF;
  239.   
  240.   ptr = pathptr->data;
  241.   *ptr++ = cube->a;
  242.   ComputePoints( cube, count, ptr );
  243. }
  244.  
  245.  
  246. /* This routine draws a cubic with the given fill */
  247. void DrawCubic( const cubic *cube, gxShapeFill theFill )
  248. {
  249.   gxShape sh = NewCubic( cube );
  250.   
  251.   if (theFill != GXGetShapeFill(sh))
  252.     GXSetShapeFill(sh, theFill);
  253.   GXDrawShape( sh );
  254.   GXDisposeShape( sh );
  255. }
  256.  
  257.  
  258. /* This routine sets the points inside of a gxPath to be those of the given cubic */
  259. void SetCubic( gxShape dest, const cubic *cube )
  260. {
  261.   smallPath   pathrec;
  262.  
  263.   CubicPath( &pathrec, cube, xCountQuadratics( cube ) );
  264.   GXSetPaths( dest, (gxPaths *) &pathrec );
  265. }
  266.  
  267.  
  268. /* This routine makes a new cubic that has a tolerance of one pixel. */
  269. gxShape NewCubic( const cubic *cube )
  270. { 
  271.   smallPath   pathrec;
  272.  
  273.   CubicPath( &pathrec, cube, xCountQuadratics( cube ) );
  274.   return GXNewPaths((gxPaths *) &pathrec );
  275. }
  276.  
  277.  
  278. /* This routine is the same as above except that it has an optional parameter for determining how many points to
  279.    include in a gxPath.  The number determines the number of points 'off' the gxCurve which are needed.
  280.  
  281.   If you use this routine you should link it in with another which determines the number of points to be used.
  282.   Here is an example that depends on a global variable 'gerror' of type extended.  Also, see the 'optimized'
  283.   example for 'xCountQuadratics' above.
  284. */  
  285. #ifdef NewCubic2Defined
  286.   #include <math.h>
  287.   
  288.   #ifdef THINK_C
  289.     #define extended long double
  290.     #define power pow
  291.   #endif
  292.   
  293.   #define FixedToExtended(a) ((extended)(a) / fixed1)
  294.   
  295.   extended gerror = 1.0;
  296.   
  297.   static long CountQuadratics( const cubic *cube )
  298.   {
  299.     extended ax = FixedToExtended( - cube->a.x + 3 * cube->b.x - 3 * cube->c.x + cube->d.x );
  300.     extended ay = FixedToExtended( - cube->a.y + 3 * cube->b.y - 3 * cube->c.y + cube->d.y );
  301.     extended a = sqrt( ax * ax + ay * ay );
  302.     extended n = power( ( a / ( 20.0 * gerror ) ), 1.0 / 3.0 );
  303.     long count = ceil( n );
  304.   
  305.     if( count <= 0 ) 
  306.       count += 1;
  307.     return count;
  308.   }
  309.   
  310.   gxShape NewCubic2( const cubic *cube, const long count );
  311.   gxShape NewCubic2( const cubic *cube, const long count )
  312.   { 
  313.     smallPath   pathrec;
  314.   
  315.     CubicPath( &pathrec, cube, ( count <= 0 ) ? CountQuadratics( cube ) : count );
  316.     return  GXNewPaths((gxPaths *) &pathrec );
  317.   }
  318.   #ifdef THINK_C
  319.     #undef extended
  320.   #endif
  321.   
  322.   #undef FixedToExtended
  323. #endif
  324.